CODE 55. Subsets

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/01/2013-10-01-CODE 55 Subsets/

访问原文「CODE 55. Subsets」

Given a set of distinct integers, S, return all possible subsets.Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
IfS=[1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

public ArrayList<ArrayList<Integer>> subsets(int[] S) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == S || S.length <= 0) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		result.add(new ArrayList<Integer>());
		return result;
	}
	Arrays.sort(S);
	ArrayList<Integer> sList = new ArrayList<Integer>();
	for (int i = 0; i < S.length; i++) {
		sList.add(S[i]);
	}
	
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	for (int i = 0; i < S.length; i++) {
		ArrayList<Integer> element = new ArrayList<Integer>();
		element.add(S[i]);
		result.add(element);
	}
	int start = 0;
	int end = result.size();
	for (int num = 2; num <= S.length; num++) {
		for (int i = start; i < end; i++) {
			ArrayList<Integer> oldElement = result.get(i);
			for (int j = sList
					.indexOf(oldElement.get(oldElement.size() - 1)) + 1; j < S.length; j++) {
				ArrayList<Integer> element = new ArrayList<Integer>();
				element.addAll(oldElement);
				element.add(S[j]);
				result.add(element);
			}
		}
		start = end;
		end = result.size();
	}
	result.add(new ArrayList<Integer>());
	return result;
}